|
A non-blocking linked list is an example of non-blocking data structures designed to implement a linked list in shared memory using synchronization primitives: * Compare-and-swap * Fetch-and-add * Load-link/store-conditional Several strategies for implementing non-blocking lists have been suggested. ==Review: linked lists== (Singly) linked lists are fundamental data structures that are widely used as is, or to build other data structures. They consist of "nodes", or "links", that are put in some order indicated by a "next" pointer on each node. The last node in the list (the "tail") has a next pointer. The first node (the "head") is a sentinel: it stores no interesting information and is only used for its pointer. The operations that must be supported on lists are as follows. * Given a node that is not yet part of the list, and a pointer to a node in the list (perhaps the head), ''insert'' after . * Given a pointer , ''delete'' from the list. Both operations must support concurrent use: two or more threads of execution must be able to perform insertions and deletions without interfering with each other's work (see diagram). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Non-blocking linked list」の詳細全文を読む スポンサード リンク
|